package com.hdu.other.dp.maxIncLen;

import java.util.Arrays;
import java.util.Comparator;

public class lc646 {
    class Solution {
        public int findLongestChain(int[][] pairs) {
            Arrays.sort(
                    pairs,
                    Comparator.comparingInt(a -> a[0])
            );
            int len = 0;
            int n = pairs.length;
            int[] ends = new int[n];
            for (int[] pair : pairs) {
                int find = bs(ends, len, pair[0]);
                if (find == -1) {
                    ends[len++] = pair[1];
                } else {
                    ends[find] = Math.min(ends[find], pair[1]);
                }
            }
            return len;
        }

        int bs(int[] ends, int len, int target) {
            int l = 0, r = len - 1, ans = -1;
            while (l <= r) {
                int mid = l + (r - l) / 2;
                if (ends[mid] >= target) {
                    ans = mid;
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            }
            return ans;
        }
    }
}
